package main

// 131. 分割回文串
func main() {
	s := "aab"
	ans := partition(s)
	for _, permuteNum := range ans {
		for _, num := range permuteNum {
			print(num, ",")
		}
		println()
	}
}

func partition(s string) (ans [][]string) {
	// 新增记忆画搜索数组，ans[i][j] i到j是不是回文
	var res [][]string
	n := len(s)
	f := make([][]bool, n) // 回文串字典

	for i := range f {
		f[i] = make([]bool, n)
		f[i][i] = true
	}

	// 根据动态规划算法 获取回纹子串
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = (s[i] == s[j] && j-i < 2) || (s[i] == s[j] && f[i+1][j-1])
		}
	}

	var split []string
	var dfs func(idx int)
	dfs = func(idx int) {
		if idx == n {
			res = append(res, append([]string{}, split...))
			return
		}
		for i := idx; i < n; i++ {
			if f[idx][i] {
				split = append(split, s[idx:i+1])
				dfs(i + 1)
				split = split[0 : len(split)-1]
			}
		}
	}

	dfs(0)

	return res
}

/*
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

*/
